/*
https://leetcode-cn.com/problems/valid-triangle-number/solution/you-xiao-san-jiao-xing-de-ge-shu-by-leet-t2td/
 */
import java.util.Arrays;

public class Solution611 {
    public int triangleNumber(int[] nums) {
        int ans=0;
        int n=nums.length;
        Arrays.sort(nums);
        int start=0;
        while (start<n && nums[start]==0){
            start++;
        }
        for (int i=start;i<n-2;i++){
            int k=i+1;
            for (int j=i+1;j<n-1;j++){
                while (k+1<n && nums[k+1]<nums[i]+nums[j]){
                    k++;
                }
                ans=ans+(k-j);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution611().triangleNumber(new int[]{2,2,3,4}));
    }
}
